#include "SqList.h"

/**
 * 初始化空的顺序表
 */
Status SqList::InitList(void)
{
    elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!elem)
        exit(OVERFLOW);

    memset(elem, 0, LIST_INIT_SIZE * sizeof(ElemType));

    listsize = LIST_INIT_SIZE;
    length = 0;

    return OK;
}

SqList::~SqList()
{
    listsize = 0;
    length = 0;
}

/**
 * 销毁顺序表
 */
Status SqList::DestoryList(void)
{
    if (elem)
        free(elem);

    elem = nullptr;
    length = 0;
    listsize = 0;

    return OK;
}

/**
 * 将顺序表设置为空表
 */
Status SqList::ClearList(void)
{
    length = 0;

    return OK;
}

/**
 * 判断顺序表是否为空表
 */
Status SqList::ListEmpty(void)
{
    if (length == 0)
        return OK;
    else
        return FALSE;
}

/**
 * 返回顺序表中元素的个数
 */
int SqList::ListLength(void)
{
    return length;
}

/**
 * 返回顺序表中第i个元素
 * i的编号从0开始
 */
Status SqList::GetElem(int i, ElemType *e)
{
    if (i < 0 || i > length)
        return FALSE;

    *e = elem[i];

    return OK;
}

/**
 * 返回顺序表中第一个与元素e满足compare关系的位号
 */
int SqList::LocateElem(ElemType e, Status(*compare)(ElemType, ElemType))
{
    int i;

    for (i = 0; i < length; ++i)
        if (compare(e, elem[i]))
            break;

    if (i != length)
        return i;

    return 0;
}

/**
 * 返回元素cur的前驱
 */
Status SqList::PriorElem(ElemType cur, ElemType *prev)
{
    int i;

    if (length <= 1)
        return FALSE;

    for (i = 0; i < length; ++i) {
        if (elem[i] == cur)
            break;
    }

    /* 只有一个元素或者超出顺序表的长度  */
    if ((i == 0) || (i == length))
        return FALSE;

    *prev = elem[i-1];

    return OK;
}

/**
 * 返回元素cur的后继
 */
Status SqList::NextElem(ElemType cur, ElemType *next)
{
    int i;

    if (length <= 1)
        return FALSE;

    for (i = 0; i < length; ++i) {
        if (elem[i] == cur)
            break;
    }

    /* 只有一个元素或者超出顺序表的长度  */
    if ((i == 0) || (i == length))
        return FALSE;

    *next = elem[i+1];

    return OK;
}

/**
 * 在第i个位置插入元素e
 */
Status SqList::ListInsert(int i, ElemType e)
{
    int j;

    if (i < 0 || i > length)
        return FALSE;

    if (length >= listsize) {
        ElemType *tmp = (ElemType*)realloc(elem, sizeof(ElemType) * (listsize + LIST_INCREMENT));
        if (tmp == nullptr)
            exit(OVERFLOW);

        listsize += LIST_INCREMENT;
        elem = tmp;
    }

    /* 向后移动元素位置 */
    for (j = length-1; j >= i; j--)
        elem[j+1] = elem[j];

    /* 第i个元素前面插入 */
    elem[i] = e;

    length++;

    return OK;
}

/**
 * 删除顺序表中的第i个位置元素，并保存在e中
 * i的编号从1开始
 */
Status SqList::ListDelete(int i, ElemType *e)
{
    int j;

    if (i < 0 || i > length)
        return FALSE;

    *e = elem[i-1];

    for (j = i; j < length; ++j)
        elem[j-1] = elem[j];

    length--;

    return OK;
}

/**
 * 遍历顺序表
 */
Status SqList::ListTraverse(void)
{
    for (int i = 0; i < length; ++i)
        print(&elem[i]);

    printf("\n");

    return OK;
}

/**
 * 合并两个线性表
 * 将i线性表Lb中不在La中的数据元素插入到La中
 */
Status SqList::ListMerge(List *Lb)
{
    ElemType e;
    int lbLength = Lb->ListLength();

    for (int i = 0; i < lbLength; ++i) {
        Lb->GetElem(i, &e);
        if (!LocateElem(e, equal))
            ListInsert(length, e);
    }

    return OK;
}
